home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Graphics⁄Sound / RTrace-1.0-src / csg.c < prev    next >
Text File  |  1992-09-17  |  8KB  |  273 lines
  1. /*
  2.  * Copyright (c) 1988, 1992 Antonio Costa, INESC-Norte.
  3.  * All rights reserved.
  4.  *
  5.  * This code received contributions from the following people:
  6.  *
  7.  *  Roman Kuchkuda      - basic ray tracer
  8.  *  Mark VandeWettering - MTV ray tracer
  9.  *  Augusto Sousa       - overall, shading model
  10.  *  Craig Kolb          - CSG
  11.  *
  12.  * Redistribution and use in source and binary forms are permitted
  13.  * provided that the above copyright notice and this paragraph are
  14.  * duplicated in all such forms and that any documentation,
  15.  * advertising materials, and other materials related to such
  16.  * distribution and use acknowledge that the software was developed
  17.  * by Antonio Costa, at INESC-Norte. The name of the author and
  18.  * INESC-Norte may not be used to endorse or promote products derived
  19.  * from this software without specific prior written permission.
  20.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  21.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  22.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  23.  */
  24. #include "defs.h"
  25. #include "extern.h"
  26. #include "csg.h"
  27.  
  28. /**********************************************************************
  29.  *    RAY TRACING - CSG - Version 7.3.1                               *
  30.  *                                                                    *
  31.  *    MADE BY    : Antonio Costa, INESC-Norte, June 1992              *
  32.  *    MODIFIED BY: Antonio Costa, INESC-Norte, July 1992              *
  33.  **********************************************************************/
  34.  
  35. /***** CSG *****/
  36. tree_struct tree;
  37. hit_struct hit_global;
  38.  
  39. void
  40. csg_copy_hit(hit_from, hit_to)
  41.   hit_ptr         hit_from, hit_to;
  42. {
  43.   REG int         i;
  44.  
  45.   hit_to->nodes = hit_from->nodes;
  46.   for (i = 0; i < hit_from->nodes; POSINC(i))
  47.     STRUCT_ASSIGN(hit_to->data[i], hit_from->data[i]);
  48. }
  49. static unsigned int
  50. csg_enter(position, vector, hit)
  51.   xyz_ptr         position, vector;
  52.   hit_ptr         hit;
  53. {
  54.   xyz_struct      tmp_position, normal;
  55.  
  56.   if (hit->data[0].enter != 0)
  57.     return (hit->data[0].enter - 1);
  58.   tmp_position.x = position->x + hit->data[0].distance * vector->x;
  59.   tmp_position.y = position->y + hit->data[0].distance * vector->y;
  60.   tmp_position.z = position->z + hit->data[0].distance * vector->z;
  61.   if (hit->data[0].object->object_type == CSG_TYPE)
  62.     csg_copy_hit(hit, &hit_global);
  63.   OBJECT_NORMAL(&tmp_position, hit->data[0].object, &normal);
  64.   if (DOT_PRODUCT(normal, *vector) < 0.0)
  65.     return 1;
  66.   return 0;
  67. }
  68. static void
  69. csg_add_hit(hit, distance, vector, object, tree)
  70.   hit_ptr         hit;
  71.   real            distance;
  72.   xyz_ptr         vector;
  73.   object_ptr      object;
  74.   tree_ptr        tree;
  75. {
  76.   if (hit->nodes == CSG_NODES_MAX)
  77.     runtime_abort("too many CSG HIT NODES");
  78.   hit->data[hit->nodes].distance = distance;
  79.   STRUCT_ASSIGN(hit->data[hit->nodes].vector,  *vector);
  80.   hit->data[hit->nodes].object = object;
  81.   hit->data[hit->nodes].enter = 0;
  82.   STRUCT_ASSIGN(hit->data[hit->nodes].tree, *tree);
  83.   POSINC(hit->nodes);
  84. }
  85.  
  86. boolean
  87. csg_union(position, vector, hit1, hit2, distance1, distance2,
  88.           hit, distance)
  89.   xyz_ptr         position, vector;
  90.   hit_ptr         hit1, hit2;
  91.   real            distance1, distance2;
  92.   hit_ptr        *hit;
  93.   real           *distance;
  94. {
  95.   REG real        distance3;
  96.   hit_struct      hit3;
  97.   hit_ptr         hit_tmp;
  98.  
  99.   while (TRUE)
  100.   {
  101.     if ((hit2->nodes == 0) OR(csg_enter(position, vector, hit2) != 0))
  102.     {
  103.       /* Hit 1st */
  104.       *hit = hit1;
  105.       *distance = distance1;
  106.       CSG_SET_ENTER(hit1, csg_enter(position, vector, hit1));
  107.       return FALSE;
  108.     }
  109.     hit3.nodes = 0;
  110.     distance3 = object_intersect(hit1->data[hit1->nodes - 1].object,
  111.                  position, vector, &hit3,
  112.                  distance2 + threshold_distance);
  113.     if (distance3 < distance2 + threshold_distance)
  114.     {
  115.       /* Leaving 2nd */
  116.       *hit = hit2;
  117.       *distance = distance2;
  118.       CSG_SET_ENTER(hit2, 0);
  119.       return FALSE;
  120.     }
  121.     hit_tmp = hit1;
  122.     hit1 = hit2;
  123.     hit2 = hit_tmp;
  124.     distance1 = distance2;
  125.     csg_copy_hit(&hit3, hit2);
  126.     distance2 = distance3;
  127.   }
  128. }
  129. boolean
  130. csg_subtraction(position, vector, hit1, hit2, distance1, distance2,
  131.                 hit, distance)
  132.   xyz_ptr         position, vector;
  133.   hit_ptr         hit1, hit2;
  134.   real            distance1, distance2;
  135.   hit_ptr        *hit;
  136.   real           *distance;
  137. {
  138.   REG real        distance3;
  139.   hit_struct      hit3;
  140.  
  141.   while (TRUE)
  142.   {
  143.     if (distance1 < distance2)
  144.     {
  145.       if ((hit2->nodes == 0) OR(csg_enter(position, vector, hit2) != 0))
  146.       {
  147.         /* Hit 1st */
  148.         *hit = hit1;
  149.         *distance = distance1;
  150.         CSG_SET_ENTER(hit1, csg_enter(position, vector, hit1));
  151.         return FALSE;
  152.       }
  153.       hit3.nodes = 0;
  154.       distance3 = object_intersect(hit1->data[hit1->nodes - 1].object,
  155.                                    position, vector, &hit3,
  156.                                    distance2 + threshold_distance);
  157.       if (distance3 < distance2 + threshold_distance)
  158.         /* Miss */
  159.         return TRUE;
  160.       distance1 = distance3;
  161.       csg_copy_hit(&hit3, hit1);
  162.       continue;
  163.     }
  164.     if (hit1->nodes == 0)
  165.       /* Miss */
  166.       return TRUE;
  167.     if (csg_enter(position, vector, hit1) == 0)
  168.     {
  169.       /* Hit 2nd inverted */
  170.       *hit = hit2;
  171.       *distance = distance2;
  172.       CSG_SET_ENTER(hit2, NOT csg_enter(position, vector, hit2));
  173.       return FALSE;
  174.     }
  175.     hit3.nodes = 0;
  176.     distance3 = object_intersect(hit2->data[hit2->nodes - 1].object,
  177.                                  position, vector, &hit3,
  178.                                  distance1 + threshold_distance);
  179.     if (distance3 < distance1 + threshold_distance)
  180.     {
  181.       /* Entering 1st */
  182.       *hit = hit1;
  183.       *distance = distance1;
  184.       CSG_SET_ENTER(hit1, 1);
  185.       return FALSE;
  186.     }
  187.     distance2 = distance3;
  188.     csg_copy_hit(&hit3, hit2);
  189.   }
  190. }
  191. boolean
  192. csg_intersection(position, vector, hit1, hit2, distance1, distance2,
  193.                  hit, distance)
  194.   xyz_ptr         position, vector;
  195.   hit_ptr         hit1, hit2;
  196.   real            distance1, distance2;
  197.   hit_ptr        *hit;
  198.   real           *distance;
  199. {
  200.   REG real        distance3;
  201.   hit_struct      hit3;
  202.   hit_ptr         hit_tmp;
  203.  
  204.   while (TRUE)
  205.   {
  206.     if (csg_enter(position, vector, hit2) == 0)
  207.     {
  208.       /* Hit 1st */
  209.       *hit = hit1;
  210.       *distance = distance1;
  211.       CSG_SET_ENTER(hit1, csg_enter(position, vector, hit1));
  212.       return FALSE;
  213.     }
  214.     hit3.nodes = 0;
  215.     distance3 = object_intersect(hit1->data[hit1->nodes - 1].object,
  216.                  position, vector, &hit3,
  217.                  distance2 + threshold_distance);
  218.     if (distance3 < distance2 + threshold_distance)
  219.       /* Miss */
  220.       return TRUE;
  221.     hit_tmp = hit1;
  222.     hit1 = hit2;
  223.     hit2 = hit_tmp;
  224.     distance1 = distance2;
  225.     csg_copy_hit(&hit3, hit2);
  226.     distance2 = distance3;
  227.   }
  228. }
  229.  
  230.  
  231. real
  232. object_intersect(intersect_object, position, vector, hit, min_distance)
  233.   object_ptr      intersect_object;
  234.   xyz_ptr         position, vector;
  235.   hit_ptr         hit;
  236.   real            min_distance;
  237. {
  238.   REG int         octant;
  239.   REG real        distance;
  240.   xyz_struct      tmp_position;
  241.  
  242.   tmp_position.x = position->x + min_distance * vector->x;
  243.   tmp_position.y = position->y + min_distance * vector->y;
  244.   tmp_position.z = position->z + min_distance * vector->z;
  245.   FIND_OCTANT(octant, *vector);
  246.   if (NOT octant_intersect(octant, &tmp_position, vector,
  247.                            intersect_object->min, intersect_object->max))
  248.     return 0.0;
  249.   if (CHECK_BOUNDS(intersect_object->object_type))
  250.     if (bound_intersect(&tmp_position, vector, intersect_object->min,
  251.                         intersect_object->max) <= 0.0)
  252.       return 0.0;
  253.   /* Primitive objects */
  254.   if (intersect_object->object_type != CSG_TYPE)
  255.   {
  256.     OBJECT_INTERSECT(distance, &tmp_position, vector, intersect_object);
  257.     if (distance < threshold_distance)
  258.       return 0.0;
  259.     distance += min_distance;
  260.     hit->nodes = 0;
  261.     csg_add_hit(hit, distance, vector, intersect_object, &tree);
  262.     return distance;
  263.   }
  264.   /* CSG objects */
  265.   distance = csg_sec_intersect(intersect_object, position, vector, hit,
  266.                    min_distance);
  267.   if (distance < threshold_distance)
  268.     return 0.0;
  269.   csg_add_hit(hit, distance, vector, intersect_object, &tree);
  270.   return distance;
  271. }
  272.  
  273.